\documentclass[9pt]{beamer}
\usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{animate} % animations
%\usepackage{beamerthemeWarsaw} % Modifier le th\`eme ici 
\usetheme[compress]{Singapore}
%\useoutertheme{infolines}


% * * * * * * * * * * * * * * * * * PICTURE * * * * * * * * * * * * * * * * * *
\usepackage{picture}
\setlength{\unitlength}{1mm}                                  % définition de l'unité
\setbeamertemplate{itemize item}[triangle]                     % style item
\setbeamertemplate{itemize subitem}[ball]                   % style subitem

%\renewcommand{\arraystretch}{1.4}                             % espacement des cellules du tableau 

%\definecolor{monred}{HTML}{9D0909}                            % un rouge
%\definecolor{monbleu}{HTML}{000066}                           % un bleu
%\definecolor{monvert}{HTML}{00AE00}                           % un vert

%\renewcommand{\footnoterule}{}                                % supprime le trait au dessus des footnotes
%\renewcommand{\thefootnote}{\alph{footnote}}                  % numérotation par des lettres

%**************************** Page de garde *********************************%


\author{Paul Milian \and Mothe Alexandre \and Tempier Grégory}

%\insertframenumber/\inserttotalframenumber%
    
\title{Vertex Cover}
\institute{ Universit\'e Bordeaux 1, Master II G\'enie logiciel \\ P.Duchon \\ A.Zvonkine}

\date{ 25 Janvier 2012 }

\begin{document}
\maketitle


	%*********************************** Plan of the presentation ***************************** %
	\section*{Plan}
	\begin{frame}
	  \tableofcontents[sections={2-7}]
	\end{frame} 

	%*************************** Presentation *********************************%
	\section{Presentation du sujet}

	\begin{frame}

	  \frametitle{Presentation du sujet} 
		\begin{itemize}	  
			\item Objectif : Trouver une couverture par sommets minimale.\\ 
			\begin{itemize}
				\item \textit{Couverture par sommets} : Sous ensemble de sommets contenant au moins une extrémité de chaque arête.
				\item Problème NP-complet.
			\end{itemize}
			\item Moyens utilisés : 
			\begin{itemize} % jeu des animations modifi\'es ---- pour faire cacher les autres \'el\'ements rajouter  \pause avant \item 	
				\item miniSAT
				\item Algorithmie
			\end{itemize}
		\end{itemize}
		
	\end{frame}




	%*************************** Algorithmes de génération *********************************%
	\section{Algorithmes de génération}
	
	
	
	%***Arbres****%
	\begin{frame}
	  \frametitle{Algorithmes de générations} 
	  \begin{itemize}
	  	\item Générateurs automatiques de graphes
		\begin{itemize}
		    \item Arbres
		    \item Graphes
		    \item Graphes bipartis
		    \item Graphes à petite couverture
		\end{itemize}
		\item Paramétrisation du nombre de sommets, probabilité d'arêtes, etc
		\item Données stockées sous forme de listes d'adjacences
		\end{itemize}

	\end{frame}
	
	\begin{frame}
	\frametitle{Génération d'arbres}  
		\begin{center}
			\includegraphics[scale=0.4]{generation_arbres.png}
		\end{center}
	\end{frame}

	
	\begin{frame}
	\frametitle{Génération de graphes}  
		\begin{center}
			\includegraphics[scale=0.4]{generation_graphes.png}
		\end{center}
	\end{frame}

	\begin{frame}
	\frametitle{Génération de graphe biparti}  
		\begin{center}
			\includegraphics[scale=0.4]{generation_biparti.png}
		\end{center}
	\end{frame}
	
	
	\begin{frame}
	\frametitle{Génération de graphe à petite couverture}  
		\begin{center}
			\includegraphics[scale=0.4]{generation_couverture_minimale.png}
		\end{center}
	\end{frame}
	
	
	

	%*************************** Algorithmes de résolution *********************************%
	\section{Algorithmes de résolution}	
	
	
	\begin{frame}
	  \frametitle{Algorithmes de résolution} 
	  \begin{itemize}
	  	\item Résolveurs automatiques de couverture minimale
		\begin{itemize}
		    \item Glouton pour graphes
		    \item Optimal pour arbres
		    \item 2-approché pour graphes (parcours d'arbre)
		    \item 2-approché pour graphes (élimination du voisinage)
		    \item Optimal pour graphe biparti
		    \item miniSAT
		\end{itemize}
		\item Le temps de résolution varie beaucoup selon l'algorithme
		\end{itemize}

	\end{frame}
	
	\begin{frame}
	\frametitle{Glouton pour graphes}  
		\begin{center}
			\includegraphics[scale=0.4]{glouton_1.png}
		\end{center}
	\end{frame}	
	
	\begin{frame}
	\frametitle{Glouton pour graphes}  
		\begin{center}
			\includegraphics[scale=0.4]{glouton_2.png}
		\end{center}
	\end{frame}	
		
	
	\begin{frame}
	\frametitle{Optimal pour arbres}  
	\begin{center}
			\includegraphics[scale=0.4]{optiarbres.png}
		\end{center}
	\end{frame}	
	
	\begin{frame}
	\frametitle{2-approché pour graphes (parcours d'arbre)}  
	\begin{center}
			\includegraphics[scale=0.4]{2approchegraphequelconques.png}
		\end{center}
	\end{frame}		

	\begin{frame}	
	\frametitle{2-approché pour graphes (élimination du voisinage)}  
	\begin{center}
			\includegraphics[scale=0.3]{2_approche_elimination_voisin.png}
		\end{center}
	\end{frame}		
	
	\begin{frame}	
	\frametitle{Optimal pour graphe biparti}  
	\begin{center}
			\includegraphics[scale=0.3]{flux1.png}
		\end{center}
	\end{frame}		
	
	\begin{frame}	
	\frametitle{Optimal pour graphe biparti}  
	\begin{center}
			\includegraphics[scale=0.4]{flux2.png}
		\end{center}
	\end{frame}	
	
		\begin{frame}	
	\frametitle{Optimal pour graphe biparti}  
	\begin{center}
			\includegraphics[scale=0.4]{flux3.png}
		\end{center}
	\end{frame}		
	
	\begin{frame}
	
	\frametitle{MiniSat}  	
	\begin{itemize}
	\item Transformation du problème de couverture par sommets sous la forme SAT
	\item MiniSAT résouds le problème
	\item Interprétation des résultats
	\end{itemize}

	\end{frame}		
	
\end{document}

% * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
% * * * * * * * * * * * * * * * * FIN * * * * * * * * * * * * * * * * * * * * *
% * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

